package com.cwj.algorithm.sort;

import java.util.List;

public class ShellSort {
    public static <T extends Comparable<? super T>> void sort(List<T> data){
        int n = data.size() / 2;
        int h = 1;
        // 确定最大步长
        while (h < n){
            h = 2*h + 1;
        }
        // 逐渐减少步长
        while (h >= 1){ // 每种步长
            for (int i = h; i < data.size(); i++) {// 待插入的元素
                for (int j = i; j >= h; j -= h) { // 遍历待插入的元素之前的元素
                    if(greater(data.get(j - h), data.get(j))){
                        exchange(data, j -h, j);
                    }else{
                        break;
                    }
                }
            }
            h >>= 1;
        }
    }

    public static <T extends Comparable<? super T>> void sort(T[] data){
        int n = data.length / 2;
        int h = 1;
        // 确定最大步长
        while (h < n){
            h = 2*h + 1;
        }
        // 逐渐减少步长
        while (h >= 1){ // 每种步长
            for (int i = h; i < data.length; i++) {// 待插入的元素
                for (int j = i; j >= h; j -= h) { // 遍历待插入的元素之前的元素
                    if(greater(data[j - h], data[j])){
                        exchange(data, j -h, j);
                    }else{
                        break;
                    }
                }
            }
            h >>= 1;
        }
    }

    private static <T extends Comparable<? super T>> boolean greater(T a, T b){
        return a.compareTo(b) > 0;
    }
    private static <T extends Comparable<? super T>> void exchange(List<T> data, int i, int j){
        T temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    private static <T extends Comparable<? super T>> void exchange(T[] data, int i, int j){
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
